# N皇后问题
import copy

# 注意：
# 1皇后攻击范围-同列同行左上右上
# 2enumerate的参数v是深拷贝

n = 8
a = [['.' for i in range(0, n)] for j in range(0, n)]
res = []


# print(a)

def is_valid(locations, row, col):
    # 校验是否同列
    for i, v in enumerate(locations):
        for j, v2 in enumerate(v):
            if j == col and v2 == 'Q':
                return False

    # 校验左上
    for i, v in enumerate(locations):
        for j, v2 in enumerate(v):
            if v2 == 'Q' and j == col - (row - i):  # 皇后攻击范围-同列同行左上右上
                return False
    # 校验左上
    # for i in range(0, row):
    #     if locations[i][col - (row - i)] == 'Q' and col - (row - i) >= 0: #解释见main函数
    #         return False

    # 校验右上
    for i, v in enumerate(locations):
        for j, v2 in enumerate(v):
            if v2 == 'Q' and j == col + (row - i):
                return False
    return True


def back_trace(locations, row):
    # 满足条件
    if row == n:
        res.append(copy.deepcopy(locations))
        return
        # 选择
    # print(row)
    t = locations[row]
    for i, v in enumerate(t):
        # 做选择
        if not is_valid(locations, row, i):
            continue
        t[i] = 'Q'
        back_trace(locations, row + 1)
        # 撤销选择
        t[i] = '.'


if __name__ == '__main__':
    # col - (row - i) >= 0 的解释，下标小于0会返回2
    # c = [1, 2, 3]
    # print(c[-2])
    print('start')
    back_trace(a, 0)
    print(len(res))
